package com.yiguang.algorithm.dp;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

import com.alibaba.fastjson.JSON;

/*
 * 八皇后问题
 * 问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
 * 回溯法：https://blog.csdn.net/m0_50217592/article/details/124229212
 */
public class NQueen {
	private int []queen;//存取皇后所在列的位置
	private int num;
	private int count;
	
	public NQueen(int n) {
		num = n;
		queen = new int[n];
	}
	
	public void eightQueen(int row){
        if (row==num){//当row等于8时说明八个皇后都放置好了
        	count++;
            //printQueens(queen);//打印八皇后
            return;
        }
        for(int column = 0; column < num; column++) {
           if (isOk(row,column)){//这里判断是否可以放在这个位置
        	   queen[row]=column;//放置皇后
               eightQueen(row+1);
           }
        }
    }
	
	public Boolean isOk(int row, int column) {
		int leftup=column-1;
		int rightup=column+1;
        for (int i = row-1; i >=0 ; --i) {
            if (queen[i]==column) return false;//看垂直方向是否有皇后
            if (leftup>=0){
                if (queen[i]==leftup) return false;//看左上角斜线是否有皇后
            }
            if (rightup<8){
                if (queen[i]==rightup) return false;//看右上角斜线是否有皇后
            }
            --leftup;
            ++rightup;
        }
        return true;
	}

	private void printQueens(int[] queen2) {
		for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (queen[row]==column) System.out.print("Q");
                else System.out.print("*");
            }
            System.out.println();
        }
        System.out.print(count);
        System.out.println();
		
	}
	
	public static void main(String[] args) {
		NQueen nQueen = new NQueen(4);
		nQueen.eightQueen(0);
		System.out.println(nQueen.count);
	}
}
